import java.util.*;


public class LinkedList
{
	static class Node implements Comparable
	{
		Comparable data;
		Node next;
		
		//Constructor when next is null
		Node(Comparable item)
		{
			data = item;
			next = null;
		}
		
		Node(Comparable item, Node nxt)
		{
			data = item;
			next = nxt;
		}
		
		public int compareTo(Object o)
		{
			return data.compareTo(((Node)o).data);
		}
		
		public String toString()
		{
			return data.toString();
		}
	}
	
	
	private Node head = new Node(null); //dummy header
	private Node tail; //tail doesn't matter yet
	private int size = 0;
		
	public int size()
	{
		return size;
	}
	
	public boolean isEmpty()
	{
		if (size == 0)
			return true;
		return false;
	}
	
	public void add(Comparable item)
	{
		if (head.next == null)
		{
			head.next = tail = new Node(item);
		}
		else 
		{
			Node temp = new Node(item);
			tail.next = temp;
			tail = temp;
		}
	
		size++;
	}
	
	public void addFirst(Comparable item)
	{
		head.next = new Node (item, head.next);
		
		//if it was empty
		if(size == 0)
			tail = head.next;
		
	}
	
	public boolean remove(Object item)
	{
		int index = indexOf(item);
		if (index == -1)
			return false;
		Comparable junk = remove(index);//this method returns Comparable?
		return true;
	}
	
	public Comparable remove(int index)
	{
		Comparable item = null;
		
		if (index < 0 || index > size-1)
			throw new IndexOutOfBoundsException("\nNot in the range zero to " + (size-1));
		
		Node curr = head.next;
		Node prev = head;
		
		while (index-- > 0)
		{
			prev = curr;
			curr = prev.next;
		}
		
		item = curr.data;
		prev.next = curr.next;
		
		if (curr.next == null)
			tail = prev;
		
		size--;
		
		return item;
	}
	
	public int indexOf(Object item)
	{
		Node curr = head.next;
		
		for(int index = 0; index < size; index++, curr = curr.next)
			if (curr.data.equals(item))
				return index;
		return -1;
	}
	
	public void sort()
	{
		//if empty or one entry, do nothing
		if (head.next == null || head.next.next == null)
			return;
			
		//create copy of linkedList
		LinkedList tempList = (LinkedList)this.clone();
		
		//clear linkedList
		this.head.next = null;
		
		//while tempList is not empty
		while (!tempList.isEmpty())
		{
			this.addFirst(tempList.removeBiggest());
		}
	}	
	
	private Comparable removeBiggest()
	{
		Node curr = head.next,
		     prev = null,
			  biggest = curr,
			  pred = prev;
		
		if (head.next == null)
			return null;
		prev = curr;
		curr = prev.next;	//move past front
		
		while(curr != null)
		{
			if (biggest.data.compareTo(curr.data) < 0)
			{
				biggest = curr; 
				pred = prev;
			}
			prev = curr;
			curr = prev.next;
		}
	
		if (pred == null)//if removing head
			head.next = biggest.next;
		else
			pred.next = biggest.next;
		
		if (biggest.next == null)// if removing tail
			tail = pred;
		this.size--;
		return biggest.data;
		
	}
	
	protected Object clone()
	{
		LinkedList list = new LinkedList();
		
		list.head.next = this.head.next;
		list.tail = this.tail;
		list.size = this.size;
		return list;
	}
	
	public String toString()
	{
		StringBuffer rtn = new StringBuffer("[");
		Node current = head.next;	//Note the dummy header
		
		if (current != null)			//First entry, no comma
		{
			rtn.append(String.format("%5d", current.data ));
			current = current.next;
		}
		
		int count = 2; // to account for first entry
		while (current != null)		// Subsequent entry, leading comma	
		{
			if (current.next != null)
			{
				rtn.append(String.format("%6d", current.data));
			}
			else
				rtn.append(String.format("%6d", current.data));
			current = current.next;
			if (count == 15 && current != null)
			{
				rtn.append("\n");
				count = 0; //reset for next line
			}
			count ++;
		}
		
		rtn.append("   ]");
		return rtn.toString();
	}

/**
*	This is the method that searches using linear search. It checks each node
*	one by one to see if it matches the Comparable input. List doesn't need to
*	be sorted.
*	@param sought what you are searching for
*	@return curr.data - found item
*/
	public Comparable linearSearch(Comparable sought)
	{
/*ans bl*/
		Node curr = this.head.next;
		while (curr!= null)
		{
			if(curr.data.compareTo((MyComparable)sought) == 0)
				return curr.data;
			curr = curr.next;
		}
		return null;
/*ans ab*/
	}
	
/**
*	This is the binary search method for the LinkedList class. It only excepts the 
*	sought value as a parameter. It then calls the recursive method binary search
*	to do the rest of the work
*	@param	sought what is being searched for
*	@return	the data, if and when found
*/
	public Comparable binarySearch(Comparable sought)
	{
		return binarySearch(this.head.next, this.size, sought);
	}
	
/**
*	This is the recursive binary search method. List must be sorted.
*	<p><p>
*	It checks if the list is empty,and returns 'null' if it is. If there is only one element in the list, it 
*	checks if that value is being searched for and either returns the data, if 
*	found, or returns null. 
*	<p><p>
*	If the list is bigger than one element, it traverses through the list until
*	it finds a midpoint. It then compares that node with the sought item. If the
*	item is found in the midpoint, it returns the item. If the item in the list 
*	is less than the sought item, it calls itself, passing head as head, size of 
*	the left half of the list as size, and sought as sought. If the item in the 
*	list is greater than the sought item, it calls itself, passing mid as head,
*	size of the right half of the list as size, and sought as sought. If it is
*	not found, 'null' is returned.
*	@param head beginning of list
*	@param size of smaller list
*	@param sought item
*	@return the data, if and when found
*/
	public Comparable binarySearch(Node head, int size, Comparable sought)
	{
		
		//if the list is empty
		if (size == 0)
			return null;
		//if there is only one item in the list
		if (size == 1)
		{
			if (head.data.compareTo(sought) == 0)
				return head.data;
			return null;
		}
		int leftSize = size / 2;
		int rightSize = size - leftSize;
		//get mid - if size is even, mid is the left middle
		Node mid = head;
		for (int i = 1; i < leftSize; i++)
		{
			mid = mid.next;
		}
		
		//check if mid == sought
		if (mid.data.compareTo(sought) == 0)
			return mid.data;
			
		//if sought is on the right side
		if (mid.data.compareTo(sought) < 0)
		{
			return binarySearch(mid.next, rightSize, sought); 
		}
		
		//if sought is on the left side
		if (mid.data.compareTo(sought) > 0)
		{
			return binarySearch(head, leftSize, sought);
		}
		
		return null;
	}
	
}